package com.wenhao.leetcode.hard;

import java.util.ArrayList;
import java.util.List;

/**
 * 题目：https://leetcode-cn.com/problems/permutation-sequence/
 * 排列序列
 *
 * 写代码之前，现在草稿纸上写一写算一算，花不了多长时间，但是可以让自己的代码更有逻辑，各种边界考虑得更加清楚！！
 * 不要老是急着写代码！！！
 *
 * @author Wenhao Tong
 * @date 2021/7/11 下午4:27
 */
public class LeetCode60 {
    public static void main(String[] args) {
        LeetCode60 leetCode60 = new LeetCode60();
        String permutation = leetCode60.getPermutation(9,2);
        System.out.println(permutation);
    }
    public String getPermutation(int n, int k) {
        int[] temp = new int[n];
        temp[0] = 1;
        List<Integer> numbers = new ArrayList<>();
        for (int i = 1;i < n;i++) {
            temp[i] = temp[i - 1] * i;
            numbers.add(i);
        }
        numbers.add(n);
        String result = "";
        for (int i = n - 1;i > 0;i--) {
            int index = (k - 1) / temp[i];
            result += numbers.get(index);
            k = k % temp[i] == 0 ? temp[i] : k % temp[i];
            numbers.remove(index);
        }
        result += numbers.get(0);
        return result;
    }

}
